package com.muchfish.algorithm.array;

/**
 * <a href="https://leetcode.cn/problems/move-zeroes/">题目：283. 移动零</a>
 * <br>
 * <img src="https://pic.leetcode-cn.com/9669b4ffb158eaeeee6f0cd66a70f24411575edab1ab8a037c4c9084b1c743f5-283_1.gif">
 */
public class Array2 {
    public static void main(String[] args) {
        int[] nums = {0,1,0,3,12};
        moveZeroes(nums);
    }

    /**
     * 暴力法
     * @param nums
     */
    private static void moveZeroes1(int[] nums) {
        //1.双层for循环，逢0右移交互
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i]==0){
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }
    /**
     * 推荐解法
     * 双指针（快慢指针）
     * 1.慢指针：记录非零的数
     * 2.快指针：查找到非零的数，交给慢指针
     * 3.非零的数处理完后，将多余（>slow的索引）的数置为0
     * @param nums
     */
    private static void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast]!=0){
                nums[slow] = nums[fast];
            }
            slow++;
        }
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
    /**
     * 双指针（快慢指针）
     * 1.慢指针：记录非零的数
     * 2.快指针：查找到非零的数，和慢指针互换值
     * @param nums
     */
    private static void moveZeroes2(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast]!=0){
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
        }
    }
    /**
     * 双指针（快慢指针）
     * 1.慢指针：记录非零的数
     * 2.快指针：查找到非零的数，交给慢指针，同时
     * @param nums
     */
    private static void moveZeroes3(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast]!=0){
                nums[slow] = nums[fast];
                if (slow!=fast) {
                    nums[fast] = 0;
                }
                slow++;
            }
        }
    }
}
